1. Field of the Invention
This invention relates to computing systems, and more particularly, to computer garbage collection mechanisms.
2. Description of the Relevant Art
When software programmers write applications to perform work according to an algorithm or a method, the programmers often utilize variables to reference temporary and result data. This data, which may be referred to as data objects, requires that space be allocated in computer memory. During execution of one or more applications, the amount of computer memory unallocated, or free, for data object allocation may decrease to a suboptimal level. Such a reduction in the amount of free space may decrease system performance and, eventually, there may not be any free space available. Automatic memory management techniques, such as garbage collection, may be used during application execution. Garbage collection maintains sufficient free space, identifies and removes memory leaks, copies some or all of the reachable data objects into a new area of memory, updates references to data objects as needed, and so on.
Garbage collection algorithms have design tradeoffs to accompany their benefits. For example, garbage collection algorithms typically include several steps and may be relatively time consuming. Consequently, the computing system may experience a pause while the garbage collection algorithm performs its tasks. If the garbage collector is run in real-time, or concurrent with the execution of applications, the length of the garbage collection pause may be unacceptable. In addition, the algorithm may utilize cache space during its execution. The use of cache space may in turn cause the eviction of useful information that must be re-fetched once the algorithm has finished.
Performing the steps of a garbage collection algorithm on a portion of memory, rather than the entire memory reduces the pause times associated with garbage collection. In addition, studies have shown in many software applications that most data objects die young. Therefore, one solution to the problems with garbage collection described above includes executing a garbage collection algorithm on a portion of memory with the youngest data objects. One such technique is generation garbage collection.
At a time when a garbage collection is determined to be run, some pre-processing steps are performed before the garbage collection proceeds. For example, addresses of older data objects pointing to younger data objects are computed at this time. The garbage collection algorithm subsequently uses these addresses to locate all reachable data objects. As the number and size of addresses increase, the time used for the address computation increases and may reduce the benefit of the generational garbage collection technique.
In view of the above, efficient methods and mechanisms for performing computer garbage collection are desired.